home *** CD-ROM | disk | FTP | other *** search
/ ftp.cs.arizona.edu / ftp.cs.arizona.edu.tar / ftp.cs.arizona.edu / icon / newsgrp / group93c.txt / 000001_icon-group-sender _Wed Jun 30 16:35:14 1993.msg < prev    next >
Internet Message Format  |  1994-02-02  |  1KB
  1. Received: from owl.CS.Arizona.EDU by cheltenham.CS.Arizona.EDU; Wed, 30 Jun 1993 15:48:54 MST
  2. Received: by owl.cs.arizona.edu; Wed, 30 Jun 1993 15:48:53 MST
  3. Date: Wed, 30 Jun 93 16:35:14 EDT
  4. From: Paul_Abrahams@MTS.cc.Wayne.edu
  5. To: icon-group@cs.arizona.edu
  6. Message-Id: <692691@MTS.cc.Wayne.edu>
  7. Subject: Tables versus lists
  8. Status: R
  9. Errors-To: icon-group-errors@cs.arizona.edu
  10.  
  11. Suppose that I have a "growing array" whose elements I frequently
  12. reference.  I can implement that array in Icon in either of two ways: as
  13. a list or as a table.  The construct for referencing an array element is
  14. the same in either case:  array[n].  The constructs for adding an element
  15. are different, but not that different:
  16.   push(array, element)
  17. versus
  18.   array[integer(*array+1)] := element
  19.  
  20. My question is: how do the efficiencies of these constructs compare?  I
  21. know that lists are implemented efficiently if allocated all at once, but
  22. how about the case where they grow an element at a time?  If finding an
  23. element requires a search down a linked list with hundreds of items, the
  24. table is clearly preferable; but if finding an element in the list can be
  25. done with an integer-indexed lookup, the list is clearly preferable.
  26.  
  27. This is a good example of a choice in Icon that is difficult to make
  28. intelligently without a knowledge of the implementation and that can make
  29. a great difference in performance.
  30.  
  31. Paul Abrahams
  32. Reply-To: abrahams@acm.org
  33.